/**
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    bool isMatch(string s, string p) {
        int sLen = s.size();
        int pLen = p.size();
        if (pLen == 0) {
        	return sLen == 0? true : false;
        }
        
        ;
        vector<vector<bool>> dp(sLen +1, vector<bool>(pLen + 1, false)); //dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
        dp[0][0] = true; //s 的前 0 个 肯定可以被 p 的前 0 个匹配
        
        if (sLen != 0 && (p[0] == s[0] || p[0] == '.')) {
        	dp[1][1] = true;
        }
        
        //初始化情况：s为空，p为 .*.* 的情况
        //也为下面的遍历匹配做准备工作 
        for(int i=1; i < pLen; i++)
        {
        	if(p[i] == '*' && dp[0][i - 1]) {
				
        		dp[0][i + 1] = true;
        	}
        }
        
        for(int i=0; i < sLen; i++)
        {
        	for(int j=1; j < pLen; j++)
        	{
        		/*p[j]不为'*'的情况*/
        		if (p[j] == s[i] || p[j] == '.') { 
        		
					dp[i + 1][j + 1] = dp[i][j];
					
				} 
				
				/*p[j]为'*'的情况*/
				if(p[j] == '*') {
					
					if (p[j - 1] == s[i] || p[j - 1] == '.') { //如果前一个元素匹配 或者 为任意元素
					
						dp[i + 1][j + 1] = (dp[i + 1][j - 1] || dp[i][j + 1]);
						//看 dp[i + 1][j - 1]的情况：也就是 将当前组合(.*)扔掉，看 dp[i + 1][j - 1] 的情况
						
					} else { //如果前一个元素不匹配 且不为任意元素
						dp[i + 1][j + 1] = dp[i + 1][j - 1]; //如果前一个元素不匹配，只能 将该组合(.*)扔掉 来看情况
					}
				}
			
			}
		}
					
		return dp[sLen][pLen];				
    }
};